Asynchronous Adaptation and Learning over Networks --- Part I: Modeling and Stability Analysis

摘要

In this work and the supporting Parts II [2] and III [3], we provide a ratherdetailed analysis of the stability and performance of asynchronous strategiesfor solving distributed optimization and adaptation problems over networks. Weexamine asynchronous networks that are subject to fairly general sources ofuncertainties, such as changing topologies, random link failures, random dataarrival times, and agents turning on and off randomly. Under this model, agentsin the network may stop updating their solutions or may stop sending orreceiving information in a random manner and without coordination with otheragents. We establish in Part I conditions on the first and second-order momentsof the relevant parameter distributions to ensure mean-square stable behavior.We derive in Part II expressions that reveal how the various parameters of theasynchronous behavior influence network performance. We compare in Part III theperformance of asynchronous networks to the performance of both centralizedsolutions and synchronous networks. One notable conclusion is that themean-square-error performance of asynchronous networks shows a degradation onlyof the order of $O(\nu)$, where $\nu$ is a small step-size parameter, while theconvergence rate remains largely unaltered. The results provide a solidjustification for the remarkable resilience of cooperative networks in the faceof random failures at multiple levels: agents, links, data arrivals, andtopology.